package Arrays;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _442_FindAllDuplicatesinanArray {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> resultLists = new ArrayList<Integer>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-1;i++) {
            if (nums[i] == nums[i + 1]) {
                resultLists.add(nums[i]);
            }
        }
        return resultLists;
    }

    //solution 2:use negative number to pass by one time
    public List<Integer> findDuplicates1(int[] nums) {

        List<Integer> result = new ArrayList<Integer> ();

        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) -1;
            if (nums[index] < 0) {
                result.add(Math.abs(nums[i]));
            } else {
                nums[index] = 0 - nums[index];
            }
        }

        return result;

    }
}
